package com.algorithm.ch1.cjm.dynamic;

/**
 * 买卖股票的最佳时机
 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
 * <p>
 * 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
 * <p>
 * 注意你不能在买入股票前卖出股票。
 */
public class MaxProfit {

    public static void main(String[] args) {
        int[] nums = new int[]{7,6,4,3,6,-10,-100};

        int res = maxProfit1(nums);

        System.out.println("动态规划的结果值为：" +  res);
    }

    /**
     * 动态规划
     *
     * @param prices
     * @return
     */
    public static int maxProfit1(int[] prices){

        int result = 0;
        if( prices == null || prices.length == 0 ) {
            return 0;
        }
        int minbug = prices[0];

        for (int i = 0; i < prices.length; i++) {

            result = Math.max(result, prices[i] - minbug);
            minbug = Math.min(minbug, prices[i]);
        }

        System.out.println(minbug);

        return result;
    }

    /**
     * 转化问题为求最大子数组
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {

        if (prices == null || prices.length == 0) {
            return 0;
        }

        int index = prices.length - 1;

        //股票之间的间隔
        int[] gap = new int[index];
        while (index > 0) {

            gap[index - 1] = prices[index] - prices[index - 1];
            index--;
        }

        int max = 0;

        for (int i = 0; i < gap.length; i++) {

            int sum = 0;
            for(int j = i; j < gap.length; j++){

                sum += gap[j];
                max = Math.max(sum, max);
            }

        }

        return max;
    }
}
